
#include <cstdlib>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
#include <random>

#include <pthread.h>
#include <unistd.h>

using namespace std;
#define MAX_CARS 1000


typedef unsigned int car_id_t;
typedef enum {
    SOUTH, EAST, NORTH, WEST
} dir_t;
typedef enum {
    a, b, c, d
} cross_quad_t;


const dir_t const_dir[] = {SOUTH, EAST, NORTH, WEST};// 定义方向类型和方向变量（便于用指针访问）
const dir_t left_dir[] = {WEST, SOUTH, EAST, NORTH};// 左侧的方向
const dir_t right_dir[] = {EAST, NORTH, WEST, SOUTH,};// 右侧的方向
const char str_dir[][6] = {"south", "east", "north", "west"};
dir_t current_dir; // 记录正在正在执行的方向


const cross_quad_t dir_quad1[] = {a, b, c, d};// 与方向对应的第1个区域对应
const cross_quad_t dir_quad2[] = {b, c, d, a};// 与方向对应的第2个区域对应
const cross_quad_t left_quad[] = {d, a, b, c};// 一个方向的车通行后，应该signal的车的方向

int empty_quad = 4;// 当前空闲的quad数，为0时死锁发生
int crossing_time = 200;//一辆车穿过一个quad要0.5秒，总共需要1秒

bool is_deadlock = false;

bool occupied[4] = {false, false, false, false};

pthread_t tids[MAX_CARS]; // one thread per car
pthread_t daemon_thread; // 守护线程

queue<car_id_t> dir_line[4]; // 当前四个方向的等待队列
car_id_t cur_car[4]; // 当前四个方向的车的id

/* 以下是 mutex & cond，有一些不空行代表mutex和cond结对使用 */


// 进入路口时使用,填dir_t
pthread_mutex_t from_dir_mutex[4];
pthread_cond_t from_dir_cond[4];

// 在当前车辆在第一个quad时，因为右前方有车需要等待时使用,填dir_t
pthread_mutex_t block_mutex[4];
pthread_cond_t block_cond[4];

// 检测死锁进程使用
pthread_mutex_t deadlock_mutex;
pthread_cond_t deadlock_cond;

pthread_cond_t resolve_cond; // 等待死锁被消除的cond

pthread_mutex_t occupy_mutex[4];

// 四个quad的mutex，填cross_quad_t
pthread_mutex_t quad_mutex[4];

pthread_mutex_t queue_mutex[4];


void init() {
    pthread_cond_init(&deadlock_cond, NULL);
    pthread_cond_init(&resolve_cond, NULL);

    pthread_mutex_init(&deadlock_mutex, NULL);

    for (int i = 0; i < 4; i++) {
        pthread_cond_init(&from_dir_cond[i], NULL);
        pthread_cond_init(&block_cond[i], NULL);

        pthread_mutex_init(&quad_mutex[i], NULL);
        pthread_mutex_init(&block_mutex[i], NULL);
        pthread_mutex_init(&from_dir_mutex[i], NULL);
        pthread_mutex_init(&occupy_mutex[i], NULL);
        pthread_mutex_init(&queue_mutex[i], NULL);
    }
}

void cross_the_quad() {
    usleep(crossing_time);
}

void push_cars(int push_num = 4) {

    is_deadlock = false;//当处理完最后一辆车，进行push cars的时候，才完全解开死锁

    // 随机产生唤醒方向的顺序
    static vector<dir_t> shuffled_dirs = {NORTH, SOUTH, WEST, EAST};
    random_device rd;
    mt19937 rng(rd());
    shuffle(shuffled_dirs.begin(), shuffled_dirs.end(), rng);

    for (int i = 0; i < push_num; i++) {
        dir_t dir = shuffled_dirs[i];// 当前一轮选中的方向
        if (!dir_line[dir].empty()) {// 这个方向有车在排队

            cur_car[dir] = dir_line[dir].front();
            dir_line[dir].pop();

            pthread_cond_signal(&from_dir_cond[dir]);
        }

    }
}


void *sched_car_with_dir_param(void *ptr) {
    dir_t dir = *(dir_t *) ptr; // 获取当前进程要处理的方位


    // 首先获取方位的准入权
    pthread_mutex_lock(&from_dir_mutex[dir]);
    pthread_cond_wait(&from_dir_cond[dir], &from_dir_mutex[dir]);
    pthread_mutex_unlock(&from_dir_mutex[dir]);

    car_id_t car = cur_car[dir]; //这个车所在进程的id，注意到必须要在from_dir_cond[dir]被signal后，否则id会没有及时更新



    printf("car %d from %s is going in %c\n", car, str_dir[dir], dir_quad1[dir] + 'a');
    pthread_mutex_lock(&quad_mutex[dir_quad1[dir]]);// 阻塞这个方向要走的第一个路口
    pthread_mutex_lock(&occupy_mutex[dir]);
    occupied[dir] = true;
    pthread_mutex_unlock(&occupy_mutex[dir]);
    empty_quad--;// 此处没有竞争不需要同步
    current_dir = dir;
    printf("car %d from %s has got in %c\n", car, str_dir[dir], dir_quad1[dir] + 'a');



    if (empty_quad == 0) { // 死锁将要发生
        pthread_cond_signal(&deadlock_cond); // 唤醒守护进程
        // 等待这个quad的条件变量，等到了说明死锁解决了,
        // 仍然基于第一个quad的mutex，因为此时它还在被这个线程持有
        pthread_cond_wait(&resolve_cond, &quad_mutex[dir_quad1[dir]]);

        // 第一个quad的死锁解决了
        cross_the_quad();


        pthread_mutex_lock(&quad_mutex[dir_quad2[dir]]);// 准备进入第二个quad

        pthread_mutex_lock(&occupy_mutex[dir]);
        occupied[dir] = false;
        pthread_mutex_unlock(&occupy_mutex[dir]);

        pthread_mutex_unlock(&quad_mutex[dir_quad1[dir]]);// 解锁第一个quad
        empty_quad++;

        cross_the_quad();


        pthread_mutex_unlock(&quad_mutex[dir_quad2[dir]]);// 第二个quad也出去了，马路就过去了
        printf("car %d from %s has left1\n", car, str_dir[dir]);
        printf("deadlock solved,left quad = %d\n", empty_quad);
        if (empty_quad < 4) empty_quad++;
        push_cars(4); // 解开死锁后，这是最后一辆走的车，所以需要一次push cars
        return NULL;

    }

    bool get_blocked = false;// 记录是否被右前方车block住，如果是
    // 右前方有车，获取不到第二个quad的锁

    pthread_mutex_lock(&occupy_mutex[right_dir[dir]]);
    if (occupied[right_dir[dir]]) {
        pthread_mutex_unlock(&occupy_mutex[right_dir[dir]]);
        get_blocked = true;

        // 等待被右前方的车唤醒

        printf("here,car is %d from %s is waiting for its right quad:%d\n", car, str_dir[dir], cur_car[right_dir[dir]]);
        pthread_mutex_lock(&block_mutex[dir]);
        pthread_cond_wait(&block_cond[dir], &block_mutex[dir]);
        pthread_mutex_unlock(&block_mutex[dir]);
        printf("here,car is %d from %s ,go!!\n", car, str_dir[dir]);
        //此时，它已经被右前方的车唤醒

        // 死锁的第二种情况，即目前的这辆车不是造成死锁的车
        if (is_deadlock) {

            // 尝试进入第二个quad
            pthread_mutex_lock(&quad_mutex[dir_quad2[dir]]);
            cross_the_quad();
            pthread_mutex_lock(&occupy_mutex[dir]);
            occupied[dir] = false;
            pthread_mutex_unlock(&occupy_mutex[dir]);
            empty_quad++;
            pthread_mutex_unlock(&quad_mutex[dir_quad1[dir]]);

            cross_the_quad();
            // 事实上就是无论如何，signal它左边的车
            if (current_dir == left_dir[dir]) {// 对应第一个if中的死锁情况
                pthread_cond_signal(&resolve_cond);
            } else {//第二个if，signal
                pthread_cond_signal(&block_cond[left_dir[dir]]);
            }


            pthread_mutex_unlock(&quad_mutex[dir_quad2[dir]]);
            printf("car %d from %s has left2\n", car, str_dir[dir]);
            return NULL;
        }
    }else{
        pthread_mutex_unlock(&occupy_mutex[right_dir[dir]]);
    }

    if(pthread_mutex_trylock(&quad_mutex[dir_quad2[dir]])==EBUSY){ //穿过路口时还没被占用，但要过去了就被占了，也是被阻塞了
        get_blocked = true;
        pthread_mutex_lock(&quad_mutex[dir_quad2[dir]]);// 进入第二个
    }

    cross_the_quad();
    printf("car %d from %s get the second lock!,which is %c\n", car, str_dir[dir], dir_quad2[dir] + 'a');
    empty_quad--;

    // 非常容易遗漏的一步
    // 当前的车要走的时候，事实上让出了右前方车道面前的格子
    // 如果没有这一步，右前方方向的车就只可能在push_cars的时候才能开（starvation）
    // 如果它放在后面的，当前方向的signal之后，就破坏了规则
    // 因为当前方向要让行右前方，不能先signal
    // 而放在unlock之前，是因为它竞争第二个quad（witch已经被lock住）而不是第一个
    // 放在这里能够加快下方对当前方向或左方向的signal
    if (!dir_line[right_dir[dir]].empty() && get_blocked) {
        cur_car[right_dir[dir]] = dir_line[right_dir[dir]].front();
        dir_line[right_dir[dir]].pop();
        printf("car %d is released by the left car %d\n", cur_car[right_dir[dir]], car);
        pthread_cond_signal(&from_dir_cond[right_dir[dir]]);
    }



    pthread_mutex_lock(&occupy_mutex[dir]);
    occupied[dir] = false;
    pthread_mutex_unlock(&occupy_mutex[dir]);
    empty_quad++;
    pthread_mutex_unlock(&quad_mutex[dir_quad1[dir]]);// 解锁第一个


    bool is_blocked_latter = false;
    pthread_mutex_lock(&occupy_mutex[left_dir[dir]]);
    if (occupied[left_dir[dir]]) { //左侧有车，并且在让位，就在离开之后让左侧通行
        pthread_mutex_unlock(&occupy_mutex[left_dir[dir]]);

        printf("car %d`s left is occupied by %d,let it go\n",car,cur_car[left_dir[dir]]);
        pthread_cond_signal(&block_cond[left_dir[dir]]);
    } else {// 最后才是当前方向的signal尝试
        pthread_mutex_unlock(&occupy_mutex[left_dir[dir]]);

        if (!dir_line[dir].empty() && !is_deadlock) {
            cur_car[dir] = dir_line[dir].front();
            dir_line[dir].pop();
            printf("car %d releases the same dir car\n",car);
            pthread_cond_signal(&from_dir_cond[dir]);
            is_blocked_latter = true;
        }
    }
    empty_quad++;
    cross_the_quad();

    if (current_dir == left_dir[dir]) {// 左车可能在等死锁
        printf("left car %d may be waiting on resolve\n", cur_car[left_dir[dir]]);
        pthread_cond_signal(&resolve_cond);
    }
    pthread_mutex_unlock(&quad_mutex[dir_quad2[dir]]);// 解锁第二个
    if (is_blocked_latter) pthread_cond_signal(&block_cond[dir]);
    printf("car %d from %s has left3\n", car, str_dir[dir]);


}


void *run_daemon(void *ptr) {
    printf("here at daemon\n");

    push_cars(); // 初始的push cars,启动


    while (1) {
        // 始终等待死锁出现
        pthread_mutex_lock(&deadlock_mutex);
        pthread_cond_wait(&deadlock_cond, &deadlock_mutex);
        is_deadlock = true;

        printf("Deadlock detected! current dir:%s，the waiting cars are:%d,%d,%d,%d\n",
               str_dir[current_dir], cur_car[SOUTH], cur_car[EAST], cur_car[NORTH], cur_car[WEST]);
        printf("the dir to be let go:%s\n", str_dir[left_dir[current_dir]]);
        pthread_cond_signal(&block_cond[left_dir[current_dir]]);
        pthread_mutex_unlock(&deadlock_mutex);


    }

}


int main() {


    char *cars = new char[MAX_CARS];
    cin >> cars;// 应该使用小写字符
    int i = 0;

    init();


    for (; i < strlen(cars); ++i) {
        switch (cars[i]) {
            case 'n':
                dir_line[NORTH].push(i);
                pthread_create(&tids[i], NULL, sched_car_with_dir_param, (void *) &const_dir[NORTH]);
                break;
            case 's':
                dir_line[SOUTH].push(i);
                pthread_create(&tids[i], NULL, sched_car_with_dir_param, (void *) &const_dir[SOUTH]);
                break;
            case 'w':
                dir_line[WEST].push(i);
                pthread_create(&tids[i], NULL, sched_car_with_dir_param, (void *) &const_dir[WEST]);
                break;
            case 'e':
                dir_line[EAST].push(i);
                pthread_create(&tids[i], NULL, sched_car_with_dir_param, (void *) &const_dir[EAST]);
                break;

        }
    }
    pthread_create(&daemon_thread, NULL, run_daemon, NULL);// 这个死锁检测线程是守护线程，车处理完了就可以退出
    for (i = 0; i < strlen(cars); ++i) {
        pthread_join(tids[i], NULL);
    }
    printf("\nend\n");


}

//swnnennswnenwnsnwnenwnenwsnnwn